package ds;

import java.util.LinkedList;
import java.util.List;

public class SkipList {

    private int level = 0; // 跳表的总层数
    private final int MAX_LEVEL = 32; // 最高 32 层

    private Node root = new Node(-1, MAX_LEVEL);

    /** 生成节点的层数 */
    private int genLevel() {
        int l = 1;
        // 0.5 概率 2 层；
        // 0.25 概率 3 层 ……
        while (Math.random() < 0.5) {
            l++;
        }
        level = Math.max(level, l);
        return l;
    }

    class Node {
        int key;
        int level; // 节点总层数
        Node[] nexts;

        Node(int key, int level) {
            this.key = key;
            this.level = level;
            nexts = new Node[level];
        }
    }

    public void insert(int key) {
        Node nw = new Node(key, genLevel());
        level = Math.max(nw.level, level);
        Node p = root;
        Node[] pres = new Node[nw.level];
        for (int l = level - 1; l >= 0; l--) {
            Node next;
            while ((next = p.nexts[l]) != null && key > next.key) {
                p = next;
            }
            if (l < nw.level) {
                pres[l] = p;
            }
        }
        // do insert
        for (int i = 0; i < nw.level; i++) {
            Node pre = pres[i];
            nw.nexts[i] = pre.nexts[i];
            pre.nexts[i] = nw;
        }
    }

    /**
     * 
     * @param key 关键字
     * @return 总共找到多少个
     */
    public int find(int key) {
        int cnt = 0;
        Node p = root;
        for (int l = level - 1; l >= 0; l--) {
            Node next;
            while ((next = p.nexts[l]) != null && key > next.key) {
                p = next;
            }
        }
        Node n = p.nexts[0];
        while (n != null && key == n.key) {
            cnt++;
            n = n.nexts[0];
        }
        return cnt;
    }

    public List<Integer> underline() {
        List<Integer> list = new LinkedList<>();
        Node p = root.nexts[0];
        while (p != null) {
            list.add(p.key);
            p = p.nexts[0];
        }
        return list;
    }

    public void insertDebug(int key) {
        insert(key);
        this.underline().forEach(e -> System.out.printf("->%d", e));
        System.out.println();
    }

    public static void main(String[] args) {
        // test
        SkipList skipList = new SkipList();
        int[] keys = { 3, 4, 4, 12, 6, 2, 2, 2, 37, 10, 2 };
        for (int i = 0; i < keys.length; i++) {
            skipList.insertDebug(keys[i]);
        }
        System.out.println("find 2 = " + skipList.find(2));
        System.out.println("find 6 = " + skipList.find(6));
    }
}